The invention relates generally to programmable devices. More specifically, the invention relates to generating of random number sequences in programmable electronic devices.
One technique utilized in image rendering (i.e., representing a real-world three-dimensional scene or image onto a two-dimensional screen or device) is that of random and noise function generation. Creating realistic textures for surfaces of objects when they are rendered often involves summing the amplitude of noise functions at certain locations within the space confined by the scene. These noise functions, which are usually frequency-limited, are evaluated at arbitrary locations by considering pulses (amplitudes created by the noise function) within a particular radius of those arbitrary locations.
The number of “dimensions,” d, may vary depending on the spatial characteristics of the desired noise function. For instance if a 2-D texture from a noise function is desired, then d is 2 (with coordinates x and y, for example). If a 3-D texture that is in motion is desired, then the number of dimensions d, would be 4 (with coordinates x, y, z, and t). FIG. 1 shows an arbitrarily chosen location 110 in a two-dimensional grid 100. The grid 100 is subdivided into integer multiples of both horizontal (x) and vertical (y) axes. If a given location A has coordinates (x, y) then the integer portion is represented by (ix, iy) and the fractional portion (Fx, Fy). Likewise, in grids with a 3rd dimension z, the integer portion is represented by iz, and the fractional portion by Fz. In systems using a fourth dimensional component(motion), t, has an integer representation “it” and a fractional representation Ft.
Assume, for purposes of illustration, that only a two-dimensional texture mapping is contemplated. Referring to FIG. 1, the sum of pulses at an arbitrary point A 110 is found by computing a series of (Fx, Fy, w)=Random(iAx, iAy, n) where n is variable tracking which of the pulses are being computed/generated, Fx, Fy are fractional coordinate components of the pulse being computed/generated, iAx, iAy are the integer coordinate components of the location A and w is the weight of the computed pulse. Likewise, if considering three-dimensional texture mapping, then(Fx, Fy, Fz, w)=Random(iAx, iAy, iAz, n), and if four-dimensional, then (Fx, Fy, Fz, Ft, w)=Random(iAx, iAy, iAz, iAt, n). The total number of pulses considered within a given cell can be fixed to a certain number. FIG. 1 shows each cell having two pulses, and thus exemplifies N=2. Each cell is referred to by the coordinates of its bottom-left vertex. The sum of pulses at an arbitrary location A 110, is found by summing the pulses that lie within a radius 120 of A 110. Pulses P9 and P10 are all of the total of two pulses within cell (1, 1), and these are included within the area swept by radius 120 about location A 110. Likewise, both of the pulses P7 and P8 in cell (0, 1) also lie within the area swept by radius 120 about location 110. However, in cell (2, 1), only one of the two pulses, namely pulse P12, lies within the area swept by radius 112 about location A 110. The other pulse P11, lies outside the area of interest and thus, would not contribute to the sum of pulses. Likewise, pulse P15 of cell (1, 0) lies within the area swept by radius 112 about location A 110 while pulse P16 lies outside. Pulses P13 and P14 of cell (0, 0), pulses P3 and P4 of cell (1, 2), pulses P17 and P18 of cell (2, 0), pulses P1 and P2 of cell (0, 2) and pulses P5 and P6 of cell (2, 2) lie outside the area of the circle and do not contribute to the sum of pulses.
One way of computing the location of these pulses and their weights is to generate random number sequences representing the coordinates and the weights of each pulse. If a computed pulse location lie outside of the circle (of radius 112 about point A 110), then its weight does not contribute to the sum of pulses.
FIG. 2 is an example of a conventional random number sequence generator. Assuming an input of three dimensions, the integer coordinate components, ix, iy, and iz, of a chosen point, are input to initializer 210 to produce a first state STATE0. Initializer 210 may be a hash function or similar mechanism. The state STATE0 is input to a randomizer 220 to produce a first random number Q0. In a serial fashion, the next state STATE1 is produced as an effect of randomizing STATE0 with randomizer 220. STATE1 is fed to the randomizer 230 (similar to randomizer 220) to produce a second random number Q1 as well as the next state STATE2. STATE2 is fed to the randomizer similar to randomizer 220) to produce a third random number Q2 as well as the next state STATE3. STATE3 is fed to the randomizer similar to randomizer 220) to produce a fourth random number Q3 as well as the next state. Likewise, any state STATEi needed to produce output Qi must be first produced by randomizing a state STATEi-l. Thus, such randomizers are essentially serial in nature. Where cycle time performance is critical and outputs must be produced in parallel, such techniques cannot be used. For instance, in producing the fractional coordinate components (Fx, Fy, Fz) and the weight w at the location given by those fractional coordinate components, each random number would represent one of those components. Thus, Q0 would represent Fx0, R1 would represent Fy0, Q2 would represent Fz0 and finally, Q3 would represent W0. Each of the outputs is available only after the previous states are produced. The serial nature of generating these outputs is inconvenient where performance speed is vital. Where parallel random number generators are used, and these are implemented in hardware, the cost/space of hardware logic blocks increases dramatically.
Thus, there is a need for a technique for random number generation that operates in a parallel fashion and can minimize the number of hardware blocks involved.